//给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现
//在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 
//
// 
//
// 示例 1: 
//
// 
//输入: temperatures = [73,74,75,71,69,72,76,73]
//输出: [1,1,4,2,1,1,0,0]
// 
//
// 示例 2: 
//
// 
//输入: temperatures = [30,40,50,60]
//输出: [1,1,1,0]
// 
//
// 示例 3: 
//
// 
//输入: temperatures = [30,60,90]
//输出: [1,1,0] 
//
// 
//
// 提示： 
//
// 
// 1 <= temperatures.length <= 10⁵ 
// 30 <= temperatures[i] <= 100 
// 
//
// Related Topics 栈 数组 单调栈 👍 1681 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class DailyTemperatures {
    public static void main(String[] args) {
        Solution solution = new DailyTemperatures().new Solution();
        int[] ints = solution.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73});
        System.out.println(ints);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 最直观的办法就是循环遍历数组，取比当前下标i大的第一个元素 和 i的下标相减 但是这样时间复杂度太高了
         *
         * @param temperatures
         * @return
         */
//        public int[] dailyTemperatures(int[] temperatures) {
//            int[] arr = new int[temperatures.length];
//            for (int i = 0; i < temperatures.length-1; i++) {
//                for (int j = i+1; j < temperatures.length; j++) {
//                    if (temperatures[i]< temperatures[j]){
//                        arr[i]  = j-i;
//                        break;
//                    }
//                }
//            }
//            return arr;
//        }

        /**
         * 由于上面的事件复杂度已经超时了
         * 所以我们想有没有一种方法可以 在遍历temperatures的时候就完成result[]的填充
         * 实际上我们可以这种
         * 拿个容器来保存一下之前还没有升温的，也就是没有结果的日子，遍历到今天的温度的时候，
         * 看看容器里面有没有比自己的温度小的，有的话就剔出容器
         *
         * 之前一直有个疑惑就是
         * 如果每次只是移出最后一个元素并且还是得小于当天问题的才能修改值，
         * 如果栈里面前几个栈针还有比当天温度小的怎么办？是不是就遍历不到了
         * 比如 ： 4  7  5     栈里面  现在是6
         * 其实这种情况是压根不存在的，在7的时候 已经满足我们逻辑要求，所以肯定是会把4弹出来
         * 做运算的
         * @param temperatures
         * @return
         */
        public int[] dailyTemperatures(int[] temperatures) {
            int length = temperatures.length;
            Deque<Integer> stack = new ArrayDeque<>();
            int[] arr = new int[length];
            for (int i = 0; i < length; i++) {
                while (!stack.isEmpty() && temperatures[stack.peekLast()] < temperatures[i]) {
                    Integer index = stack.pollLast();
                    arr[index] = i - index;
                }
                stack.addLast(i);
            }
            return arr;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}